/*
 * 	Author : Pallab
 * 	Prog: A.cxx
 *
 * 	Created on: 01:01:57 AM - 2013:2:22
 * "I have not failed, I have just found 10000 ways that won't work."
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;


#define foR(i,frm,upto) for( int i=(frm),_i=(upto);(i) < (_i) ; ++i )
#define foD(i,frm,upto) for( int i=(frm),_i=(upto);(i) >= (_i) ; --i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define dbg(...)       printf(__VA_ARGS__)
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

inline void wait ( double seconds ) {
    double endtime = clock() + ( seconds * CLOCKS_PER_SEC );
    while ( clock() < endtime ) {
        ;
    }
}
template<class T>
    inline T fastIn() {
    register char c=0;
    register T a=0;
    bool neg=false;
    while ( c<33 ) c=getchar();
    while ( c>33 ) {
        if ( c=='-' ) {
            neg=true;
        } else {
            a= ( a*10 ) + ( c-'0' );
        }
        c=getchar();
    }
    return neg?-a:a;
}
int const mxn=105;
int N,M,K,C;
int grid[mxn][mxn];
inline void read() {
    N=fastIn<int>(),M=fastIn<int>(),K=fastIn<int>(),C=fastIn<int>();
    foR ( i,0,N ) {
        foR ( j,0,M ) {
            grid[i][j]=fastIn<int>();
        }
    }
}
namespace EMAX_KUHN {
    int n, k;
    vector<int> g[mxn<<1];
    int mt[mxn<<1];
    char used[mxn<<1];

    bool try_kuhn ( int v ) {
        if ( used[v] )  return false;
        used[v] = true;
        for ( int i=0, j=SZ ( g[v] ); i<j; ++i ) {
            int to = g[v][i];
            if ( mt[to] == -1 || try_kuhn ( mt[to] ) ) {
                mt[to] = v;
                return true;
            }
        }
        return false;
    }

    inline int run() {
        SET ( mt,-1 );
        int cnt=0;
        for ( int v=0; v<n; ++v ) {
            SET ( used, false );
            if ( try_kuhn ( v ) ) ++cnt;

        }
        return cnt;
    }
};
inline void build_bp_graph ( int limit ) {
    foR ( i,0, ( mxn<<1 ) ) EMAX_KUHN::g[i].clear();
    EMAX_KUHN::n=N;
    EMAX_KUHN::k=M;

    foR ( i,0,N ) {
        foR ( j,0,M ) {
            int dist1 = grid[i][j];
            int dist2 = grid[i][j]+C;
            if ( dist1<=limit )
                EMAX_KUHN::g[i].push_back ( j );
            if ( dist2<=limit )
                EMAX_KUHN::g[i].push_back ( j+M );
        }
    }
}
inline void proc() {
    int lo=0,hi=1023456789;
    int bst=hi;
    while ( lo+1<hi ) {
        int mid= ( lo+hi ) >>1;
        build_bp_graph ( mid );
        int tmp = EMAX_KUHN::run();
        if ( tmp>=K ) {
            bst=min ( bst,mid );
            hi=mid;
        } else {
            lo=mid;
        }
    }
    cout<<bst<<"\n";
}
int main() {
    int kase = 1;
#if defined( xerxes_pc )
    if ( !freopen ( "in1", "r", stdin ) )
        puts ( "error opening file in " ), assert ( 0 );
    kase = 1;
#endif
    kase=fastIn<int>();
    foR ( i,0,kase ) {
        read();
        proc();
    }
    return 0;
}
// kate: indent-mode cstyle; indent-width 4; replace-tabs on; 





